#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;


class Solution {
public:
    using int_pair = pair<int, int>;
    static bool cmp(int_pair& m, int_pair& n) {
        return m.second > n.second;  // greater
    } //* 最小堆需要用 >
    
    //* 为什么用最小堆？因为我们跟堆顶最小元素比较，只要跟堆顶元素比小，
    //* 那么就小于堆中全部元素了！这样确保堆中全是 Top K 元素！

    /**
     * 只保留 top K 个元素在 MinHeap 中，则最大深度为 O(log k)。
     * 遍历【出现次数数组】需要 log(n)。
     * 时间复杂度：O(n log k)
     * 空间复杂度：O(n)
     */
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq_table;
        for (int n : nums) freq_table[n]++;
        
        // <Type, Container, Functional>
        priority_queue<int_pair, vector<int_pair>, decltype(&cmp)> pq(cmp);
        for (auto& [num, freq] : freq_table) {  // O(n) iterations
            if (pq.size() == k) {
                if (pq.top().second < freq) {
                    pq.pop();
                    pq.emplace(num, freq);
                }
            } else {
                pq.emplace(num, freq);
            }
        }
        
        // 此时堆中都是前 k 高频的元素了
        vector<int> res(k);
        for (int i=0; i<k; i++) {
            res[i] = pq.top().first;
            pq.pop();
        }

        return res;
    }
};
